#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>

#include "cboard.h"

using namespace std;

namespace sokoban
{

// Initialize static data members
uint8_t   CBoard::nBoxes     = 0;
T_DIM     CBoard::nRow       = 0;
T_DIM     CBoard::nCol       = 0;
ECell   * CBoard::mCell      = 0;
T_POS   * CBoard::goalsCells = 0;
uint16_t * CBoard::distances  = 0;

bool CBoard::originBoardCreated = false;

CBoard::CBoard( string & stringBoard )
{
  // Safety first : we assert if the very first board has already been
  // created. This should be done only once.

  ASSERT( originBoardCreated == false, "Using again CBoard(string) constructor" );

  originBoardCreated = true; // now we are sure we wont use this ctor again.

  // First parse the string to obtain size data
  string::iterator it;
  T_DIM tmpCol = 0;   // column in the actual row
  for (it = stringBoard.begin(); it < stringBoard.end(); ++it)
  {
    switch ( *it )
    {
    case '#':
    case '@':
    case '+':
    case '.':
    case ' ':
      ++tmpCol;
      break;

    case '$':
    case '*':
      ++tmpCol;
      ++nBoxes;
      break;

    case '\n':
      ++nRow;
      if ( tmpCol > nCol )
        nCol = tmpCol;
      tmpCol = 0;
      break;
    }
  }

  // Parse the string again and populate the data
  mCell       = new ECell[nRow*nCol];
  boxesCells  = new T_POS[nBoxes];
  goalsCells  = new T_POS[nBoxes];

  tmpCol     = 0;
  uint8_t  j = 0;
  uint16_t i = 0, gc = 0, bc = 0; // some indices
  for (it = stringBoard.begin(); it < stringBoard.end(); ++it)
  {
    switch ( *it )
    {
    case '#':   // wall
      mCell[i++]       = CELL_WALL;
      ++tmpCol;
      break;
    case '@':   // player
      playerCell       = i;
      mCell[i++]       = CELL_FLOOR;    // don't store dynamic info in mCell  
      ++tmpCol;
      break;
    case '+':   // player on goal
      playerCell       = i;
      goalsCells[gc++] = i;
      mCell[i++]       = CELL_GOAL;
      ++tmpCol;
      break;
    case '.':   // goal
      goalsCells[gc++] = i;
      mCell[i++]       = CELL_GOAL;
      ++tmpCol;
      break;
    case ' ':   // floor (empty cell)
      mCell[i++]       = CELL_FLOOR;
      ++tmpCol;
      break;
    case '$':   // box
      boxesCells[bc++] = i;
      mCell[i++]       = CELL_FLOOR;    // don't store dynamic info in mCell
      ++tmpCol;
      break;
    case '*':   // box on goal
      boxesCells[bc++] = i;
      goalsCells[gc++] = i;
      mCell[i++]       = CELL_GOAL;    // don't store dynamic info in mCell
      ++tmpCol;
      break;
    case '\n':
      for (j = 0; j < (nCol-tmpCol); ++j)
        mCell[i++]     = CELL_WALL;     // pad short columns with walls
      tmpCol = 0;
      break;
    }
  }

  LOG( L_CBOARD, "Original board created, with\n\t%i boxes and goals\n\t%i rows and %i columns.", nBoxes, nRow, nCol );

  // Populate playerMoves
  storeCharacterReachablePos();

  findStaticDeadlocks();

  distances = new uint16_t[ nRow * nCol * nRow * nCol ];

  //computeManhattanDistances();
  computeDjikstraPath();

  computeHeuristic();
}

CBoard::CBoard
(
  CBoard   const & pRH,
  CBoxMove const & pMove
):
  playerCell( pRH.playerCell ),
  path( pRH.path )
{
  boxesCells = new T_POS[ nBoxes ];

  memcpy( boxesCells, pRH.boxesCells, nBoxes*sizeof( T_POS ) );

  DoMove( pMove );

  storeCharacterReachablePos();

  computeHeuristic();
}

CBoard::CBoard( CBoard const & other ):
  value( other.value ),
  playerCell( other.playerCell ),
  path( other.path )
{
  boxesCells = new T_POS[ nBoxes ];

  memcpy( boxesCells, other.boxesCells, nBoxes*sizeof( T_POS ) );

  playerMoves = new CMovePool( *( other.playerMoves ) );
}

CBoard::~CBoard()
{
  // we dont free the static data allocated at the first creation of the
  // object. This is bad but saves us some time (and this resources are
  // used until the end of the program anyway).

  delete[] boxesCells;
  delete playerMoves;
}

void CBoard::DoMove(const CBoxMove &pMove)
{
  LOG( L_S_BOXES_MOVES, "Moving box id. %d", int(pMove.movedBoxIdx) );

  // Update the position of the player
  playerCell = pMove.finalPlayerPos;
  // Update the position of the moved box
  boxesCells[ pMove.movedBoxIdx ] = pMove.finalBoxPos;
  // Update the path that the player has taken to come to this state (board)
  path += pMove.ToString();
}

void CBoard::Print( const vector< T_POS > & markers ) const
{
  string stringBoard;

  // Static info of the board (walls and goals)
  vector< ECell > curBoard (mCell, mCell+nRow*nCol);

  // Position of the player
  if ( curBoard[playerCell]==CELL_GOAL )
    curBoard[playerCell] = CELL_PL_ON_GOAL;
  else
    curBoard[playerCell] = CELL_PLAYER;

  // Position of the boxes
  for (uint8_t nb = 0; nb < nBoxes; ++nb)
  {
    if ( curBoard[ boxesCells[nb] ]==CELL_GOAL )
      curBoard[ boxesCells[nb] ] = CELL_BOX_ON_GOAL;
    else
      curBoard[ boxesCells[nb] ] = CELL_BOX;
  }
  
  T_POS pR, pC;
  bool mark = false;
  for (pR = 0; pR < nRow; ++pR)
  {
    for (pC= 0; pC < nCol; ++pC)
    {
      
      mark = find(markers.begin(), markers.end(), pC+pR*nCol) != markers.end();

      if ( mark )
      {
        if ( curBoard[pR*nCol+pC]==CELL_DEADLOCK )
          printf("\e[37;41m ");
        else
          printf("\e[37;42m");
      }

      switch ( curBoard[pR*nCol+pC] )
      {
      case (CELL_WALL):
        printf("#");
        break;
      case (CELL_BOX):
        printf("$");
        break;
      case (CELL_BOX_ON_GOAL):
        printf("*");
        break;
      case (CELL_PLAYER):
        printf("@");
        break;
      case (CELL_PL_ON_GOAL):
        printf("+");
        break;
      case (CELL_FLOOR):
        printf(" ");
        break;
      case (CELL_GOAL):
        printf(".");
        break;
      case (CELL_DEADLOCK):
        if ( !mark )
          printf("\e[37;44m \e[0m");
        break;
      }

      if ( mark )
        printf("\e[0m");

    }
    printf("\n");
  }
}

bool CBoard::IsSolution() const
{
  for( int i = 0 ; i < nBoxes ; i++ )
  {
    if( !isGoal( boxesCells[i] ) )
      return false;
  }

  return true;
}

bool CBoard::isGoal(T_POS cell) const
{
  for (uint8_t i = 0; i < nBoxes; ++i)
  {
    if ( cell==goalsCells[i] )
      return true;
  }
  return false;
}

uint8_t countDigits(uint16_t n)
{
  ASSERT( n < 0, "Trying to obtain the number of digits of a negative number" );

  uint8_t ndigits = 0;

  while ( n > 0 )
  {
    n = n/10;
    ++ndigits;
  }

  return ndigits;
}

uint64_t CBoard::Hash() const
{
  uint16_t ordBoxesCells[nBoxes];
  uint16_t minReachCell;
  uint8_t  i, ndigits;
  uint64_t hash = 0;

  // Construct the hash with the position of the boxes in ascending order
  memcpy( ordBoxesCells, boxesCells, nBoxes*sizeof(uint16_t) );
  sort(ordBoxesCells, ordBoxesCells+nBoxes);
  for (i = 0; i < nBoxes; ++i)
  {
    // Append the index of the box i at the end of the hash
    ndigits = countDigits( ordBoxesCells[i] );
    hash   *= uint64_t( pow(10, ndigits) );
    hash   += ordBoxesCells[i];
  }

  // Include at the end of the hash the summary of the player's reachable area
  minReachCell = getMinimumReachablePos();
  ndigits      = countDigits( minReachCell );
  hash        *= uint64_t( pow(10, ndigits) );
  hash        += minReachCell;

#ifdef DEBUG_HASH
  LOG( LOG_DEBUG, "Hash = %lli", hash );
  LOG( LOG_DEBUG, "Position of the boxes:" );
  for (i = 0; i < nBoxes; ++i)
    LOG( LOG_DEBUG, " %i", boxesCells[i] );
  LOG( LOG_DEBUG, "Cells reachable by the player:" );
  vector< uint16_t > reachablePos = playerMoves->ToVector();
  for (uint16_t posIdx = 0; posIdx < reachablePos.size(); ++posIdx)
    LOG( LOG_DEBUG, " %i",  reachablePos[posIdx]);
#endif

  return hash;
}

uint16_t CBoard::Value() const
{
  return value;
}

bool CBoard::operator<( CBoard const & boardOther ) const
{
  return ( value < boardOther.value );
}

void CBoard::computeManhattanDistances()
{
  int nCells = nRow * nCol;

  // this is a symetric matrix : 0s on the diagonal and upper and lower
  // triangles equal.

  int curDistance;

  for( int i = 0 ; i < nCells ; i++ )
  {
    distances[ i + ( nCells * i ) ] = 0;

    for( int j = i+1 ; j < nCells ; j++ )
    {
      curDistance = abs( i / nCol - j / nCol ) + abs( i % nCol - j % nCol );

      distances[ j + ( nCells * i ) ] = curDistance;
      distances[ i + ( nCells * j ) ] = curDistance;
    }
  }
}

void CBoard::computeDjikstraPath()
{
  int nCells = nRow * nCol;

  // this is a symetric matrix : 0s on the diagonal and upper and lower
  // triangles equal.

  int distIJ, distICur, j;
  int curCell;
  queue<int> exploQueue;
  //Initialization of the distances
  for (int i = 0; i < nCells; i++)
  {
    for (int j = 0; j < nCells; j++)
    {
      distances[i + (nCells * j)] = 10000;
    }
  }
  
  for( int i = 0 ; i < nCells ; i++ )
  {
    distances[ i + ( nCells * i ) ] = 0;
    if (mCell[i] != CELL_WALL)
    {
      exploQueue.push(i);
      while (!exploQueue.empty())
      {
        curCell = exploQueue.front();
        distICur = distances[i + (nCells * curCell)];
        //Check cells up and down
        for (int col = -1; col <= 1; col += 2)
        {
          if (((curCell%nCol + col) >= 0) && ((curCell%nCol + col) <= nCol-1))
          {
            j = curCell + col;
            if (mCell[j] != CELL_WALL)
            {
              distIJ = distances[i + (nCells * j)];
              if (distIJ == 10000) 
                exploQueue.push(j);
              if (distIJ > (distICur + 1)) 
                distances[i + (nCells * j)] = distICur + 1;
            }
          }
        }
        //Check cells left and right
        for (int row = -1; row <= 1; row += 2)
        {
          if (((curCell/nCol + row) >= 0) && ((curCell/nCol + row) <= nRow-1))
          {
            j = curCell + row*nCol;
            if (mCell[j] != CELL_WALL)
            {
              distIJ = distances[i + (nCells * j)];
              if (distIJ == 10000) 
                exploQueue.push(j);
              if (distIJ > (distICur + 1)) 
                distances[i + (nCells * j)] = distICur + 1;
            }
          }
        }
        exploQueue.pop();
      }
    }
  }

#if ( LOG_LEVEL & L_HEUR )
  for( int celli = 0 ; celli < nCol*nRow ; celli++ )
  {
    for( int cellj = 0 ; cellj < nCol*nRow ; cellj++ )
    {
      cerr << distances[ celli + nCol*nRow*cellj ] << '\t';
    }
    cerr << endl;
  }
#endif
}

void CBoard::computeHeuristic()
{
  value = 0;

  T_DIM nCells = nCol * nRow;

  uint16_t curMinDistance;

  // for each box, find the nearest goal and add the distance to it to the
  // value of the board.

  for( int box = 0 ; box < nBoxes ; box++ )
  {
    LOG( L_HEUR, "Looking for nearest goal for box %d, on cell %d",
         box, boxesCells[ box ] );

    curMinDistance = 1000;

    for( int goal = 0 ; goal < nBoxes ; goal++ )
    {
      LOG( L_HEUR, ">Trying with goal %d, on cell %d", goal,
           goalsCells[ goal ] );
      LOG( L_HEUR, ">Distance is %d", 
           distances[ boxesCells[box] + ( nCells * goalsCells[goal] ) ] );

      if( distances[ boxesCells[box] + ( nCells * goalsCells[goal] ) ]
          < curMinDistance )
      {
        curMinDistance =
          distances[ boxesCells[box] + ( nCells * goalsCells[goal] ) ];
      }

      if( curMinDistance == 0 )
        // we wont find a better distance with other goals, skip to the
        // next box
        break;
    }

    value += curMinDistance;
  }

  LOG( L_HEUR, "Computed value : %d", value );
}

void CBoard::findStaticDeadlocks()
{

  // Initialization
  bool reachedCells[nCol*nRow];
  uint16_t i = 0;
  for ( i = 0 ; i < nCol*nRow ; ++i )
    reachedCells[i] = false;

  // For each goal, look for the positions that a box can be pulled
  for ( uint8_t idx = 0 ; idx < nBoxes ; ++idx )
    pullBoxBFS( reachedCells, goalsCells[idx] );

  // Mark as static deadlock all the non-reached cells
  for ( i = 0; i < nCol*nRow ; ++i )
  {
    if ( !reachedCells[i] && mCell[i]==CELL_FLOOR )
      mCell[i] = CELL_DEADLOCK;
  }   

#ifdef DEBUG_STA_DEADLOCK
  LOG( L_STA_DEADLOCK, "Displaying static deadlocks..." );
  Print();
#endif

}

void CBoard::pullBoxBFS( bool reachedCells[], T_POS initBoxPos )
{

  queue  < T_POS > boxPosToExpand;
  T_POS            curBoxPos;
  vector < T_POS > possibleMoves;
  vector < T_POS >::iterator it;

  boxPosToExpand.push( initBoxPos );
  while ( !boxPosToExpand.empty() )
  {
    curBoxPos = boxPosToExpand.front();
    boxPosToExpand.pop();
    findPossiblePullMoves( curBoxPos, possibleMoves );

    for ( it = possibleMoves.begin() ; it < possibleMoves.end() ; ++it )
    {
      if ( !reachedCells[ *it ] )
      {
        reachedCells[ *it ] = true;
        boxPosToExpand.push( *it );
      }
    }

  }
}

void CBoard::findPossiblePullMoves( T_POS boxPos, vector< T_POS > & possibleMoves )
{
  T_POS nextBoxPos, playerPos; // pos of the box and the player if the pull is valid

  possibleMoves.clear();

  // trying up
  nextBoxPos  = boxPos - nCol;
  playerPos   = boxPos - 2*nCol; 
  if ( ( nextBoxPos > 0 ) && ( mCell[nextBoxPos] != CELL_WALL ) )
  {
    if ( ( playerPos > 0 ) && ( mCell[playerPos] != CELL_WALL ) )
      possibleMoves.push_back( nextBoxPos );
  }
  // trying down
  nextBoxPos  = boxPos + nCol;
  playerPos   = boxPos + 2*nCol;
  if ( ( nextBoxPos < nCol*nRow ) && ( mCell[nextBoxPos] != CELL_WALL ) )
  {
    if ( ( playerPos < nCol*nRow ) && ( mCell[playerPos] != CELL_WALL ) )
      possibleMoves.push_back( nextBoxPos );
  }
  // trying left
  nextBoxPos  = boxPos - 1;
  playerPos   = boxPos - 2;
  if ( ( nextBoxPos > 0 ) && ( mCell[nextBoxPos] != CELL_WALL ) )
  {
    if ( ( playerPos > 0 ) && ( mCell[playerPos] != CELL_WALL ) )
      possibleMoves.push_back( nextBoxPos );
  }
  // trying right
  nextBoxPos  = boxPos + 1;
  playerPos   = boxPos + 2;
  if ( ( nextBoxPos < nCol*nRow ) && ( mCell[nextBoxPos] != CELL_WALL ) )
  {
    if ( ( playerPos < nCol*nRow ) && ( mCell[playerPos] != CELL_WALL ) )
      possibleMoves.push_back( nextBoxPos );
  }
}

void CBoard::findCharacterReachablePos // 3rd time
(
  T_POS from,
  EMoveElem fromMove,
  CMovePool * movesAlreadyDone
) const
{

  array< EMoveElem, 4  > nextMoves;

  MoveMap::iterator it = movesAlreadyDone->Insert( from, fromMove, nCol );

  // if we successfully inserted the move in the structure, we expand from
  // it.
  if( it != movesAlreadyDone->End() )
  {
    T_POS curPos = it->first;

    uint8_t nNextMoves = tryElemMoves( curPos , nextMoves);

    LOG( L_S_PLAYER_MOVES, "F : Expanding %i with %i children", curPos, nNextMoves );

    for( uint8_t i = 0 ; i < nNextMoves ; i++ )
    {
      LOG( L_S_PLAYER_MOVES, "\tmovement %c from %i", ( EMoveElem )nextMoves[ i ], curPos );

      findCharacterReachablePos( curPos, nextMoves[ i ], movesAlreadyDone );
    }
  }
  else
  {
    LOG( L_S_PLAYER_MOVES, "F : We already went there. Returning." );
  }
}

void CBoard::storeCharacterReachablePos()
{
  LOG( L_S_PLAYER_MOVES, "Entering storeCharacterReachablePos" );

  playerMoves = new CMovePool;
  findCharacterReachablePos( playerCell, M_NONE, playerMoves );
  LOG( L_S_PLAYER_MOVES, ">> Player moves computed." );

#if ( LOG_LEVEL & L_S_PLAYER_MOVES )
  LOG( L_S_PLAYER_MOVES, "Displaying player moves...\n" );
  Print( playerMoves->ToVector() );
#endif 
}

uint16_t CBoard::getMinimumReachablePos() const
{
  vector< T_POS > reachablePos = playerMoves->ToVector();

  T_POS minReachablePos = *min_element( reachablePos.begin(), reachablePos.end() );

  return minReachablePos;
}

uint8_t CBoard::tryElemMoves
(
  T_POS fromPos,
  array< EMoveElem, 4 > & nextMoves
) const
{
  uint8_t nMoves = 0;

  // try right
  if( isFreeFor( fromPos + 1 , PLAYER ) )
    nextMoves[ nMoves++ ] = ( M_R );

  // try left
  if( isFreeFor( fromPos - 1 , PLAYER ) )
    nextMoves[ nMoves++ ] = ( M_L );

  // try up
  if( isFreeFor( fromPos - nCol , PLAYER ) )
    nextMoves[ nMoves++ ] = ( M_U );

  // try down
  if( isFreeFor( fromPos + nCol , PLAYER ) )
    nextMoves[ nMoves++ ] = ( M_D );

  return nMoves;
}

bool CBoard::isFreeFor( T_POS position, EWHO who , uint8_t boxIdx ) const
{
  // is there a box here ?
  for( uint8_t i = 0 ; i < nBoxes ; i++ )
  {
    // if so, no one can walk here
    if( position == boxesCells[ i ] )
      return false;
  }

  ECell at_i = At( position );

  if( at_i == CELL_WALL )
    return false;

  // if there is no box here
  //   if it's a static deadlock, just the player can go there
  if( at_i == CELL_DEADLOCK )
  {
    if ( who & PLAYER )  return true;
    if ( who & BOX    )  return false;
  }

  // if a box would create a dynamic deadlock in position, just the player can go  
  if ( who & BOX )
    return !DetectDynamicDeadlock( position , boxIdx );

  // if none of the previous conditions were met then also box can go here.
  return true;
}

void CBoard::FindPossibleBoxesMoves(vector<CBoxMove> &pMoves) const
{
  LOG( L_S_BOXES_MOVES, ">> Entering FindPossibleBoxesMoves" );

  T_POS boxPos;
  MoveMap::const_iterator playerMoveIt;
  MoveMap::const_iterator playerMoveEnd = playerMoves->End();

  LOG( L_S_BOXES_MOVES, ">> Moving the boxes around..." );

  for( uint8_t i = 0 ; i < nBoxes ; i++ )
  {
    boxPos = boxesCells[ i ];

    LOG( L_S_BOXES_MOVES, "\tTrying to move box %i at position %i", i, boxPos );

    // trying up
    if( isFreeFor( boxPos - nCol , BOX , i ) )
    {
      playerMoveIt = playerMoves->CanGoThere( boxPos + nCol );

      if( playerMoveIt != playerMoveEnd )
      {
        LOG( L_S_BOXES_MOVES, "\t\tBox %i can move up.", i );
        pMoves.push_back(
            CBoxMove( playerMoveIt, i, boxPos - nCol, boxPos, M_U ) );
      }
    }
    // trying down
    if( isFreeFor( boxPos + nCol , BOX , i ) )
    {
      playerMoveIt = playerMoves->CanGoThere( boxPos - nCol );

      if( playerMoveIt != playerMoveEnd )
      {
        LOG( L_S_BOXES_MOVES, "\t\tBox %i can move down.", i );
        pMoves.push_back(
            CBoxMove( playerMoveIt, i, boxPos + nCol, boxPos, M_D ) );
      }
    }
    // trying left
    if( isFreeFor( boxPos - 1 , BOX , i ) )
    {
      playerMoveIt = playerMoves->CanGoThere( boxPos + 1 );

      if( playerMoveIt != playerMoveEnd )
      {
        LOG( L_S_BOXES_MOVES, "\t\tBox %i can move left.", i );
        pMoves.push_back(
            CBoxMove( playerMoveIt, i, boxPos - 1, boxPos, M_L ) );
      }
    }
    // trying right
    if( isFreeFor( boxPos + 1 , BOX , i ) )
    {
      playerMoveIt = playerMoves->CanGoThere( boxPos - 1 );

      if( playerMoveIt != playerMoveEnd )
      {
        LOG( L_S_BOXES_MOVES, "\t\tBox %i can move right.", i );
        pMoves.push_back(
            CBoxMove( playerMoveIt, i, boxPos + 1, boxPos, M_R ) );
      }
    }
  }

#if ( LOG_LEVEL & L_S_BOXES_MOVES )
  vector< T_POS > boxMarkers( pMoves.size() );

  for( unsigned int i = 0 ; i < pMoves.size() ; i++ )
    boxMarkers[ i ] = pMoves[ i ].finalBoxPos;

  LOG( L_S_BOXES_MOVES, "Displaying boxes moves..." );
  Print( boxMarkers );
#endif

}


void CBoard::findStaticDeadlocksBis()
{
	//TODO improve to find complex & tricky deadlocks
	// /!\first draft 
	//-> find only corners and walls between corners
	//-> have to clean it


	//Useful constants
	int8_t WALL_NORTH = ( 1 << 0 );
	int8_t WALL_EAST = ( 1 << 1 );
	int8_t WALL_SOUTH = ( 1 << 2 );
	int8_t WALL_WEST = ( 1 << 3 );
	int8_t WALL_MASK = WALL_NORTH + WALL_WEST + WALL_SOUTH + WALL_EAST;
	int8_t POSSIBLE_DEADLOCK = ( 1 << 4 );
	int8_t CORNER = ( 1 << 5 );
	int8_t DEADEND = ( 1 << 6 );
	//int8_t GOAL = ( 1 << 7 );
	
	//note : the constants WALL_ are used to know the walls surounding the cellPos
	//           north = 1
	//  west = 8          east = 2
	//           south = 4
	//By summing these values, we easily know if the cell is 
	//a corner -> value = 0 % 3
	//a corridor -> value = 0 % 5


	int8_t mWorkingBoard[nRow*nCol];
	//Initializing working board
	for( int i = 0 ; i < nRow*nCol ; i++ )
	{
		/*switch (mCell[i])
		{
			case CELL_WALL :
				mWorkingBoard[i] = WALL;
				break;
			case CELL_GOAL :
				mWorkingBoard[i] = GOAL;
				break;
			case CELL_FLOOR :
				mWorkingBoard[i] = 0;
		}*/
		mWorkingBoard[i] = 0;
	}

	for( int row = 0 ; row < nRow ; row++ )
	{
		for( int col = 0 ; col < nCol ; col++ )
		{
			int cellPos = row*nCol + col;
			int8_t cellSituation = 0;
			//TODO /!\ here we assume that the board is surounded by walls
			// have to check if not (or else we can be out of the board)
			if( mCell[cellPos] != CELL_WALL && mCell[cellPos] != CELL_GOAL )
			{
				//check if there is wall around the cell 
				//(NB : a dead-end is like a wall)
				cellSituation = 
					(( (mCell[cellPos-1] == CELL_WALL) ||
					(mWorkingBoard[cellPos-1] & DEADEND) ) ? WALL_WEST : 0) +
					(( mCell[cellPos+1] == CELL_WALL ) ? WALL_EAST : 0) +
					(( (mCell[cellPos-nCol] == CELL_WALL) ||
					(mWorkingBoard[cellPos-nCol] & DEADEND) ) ? WALL_NORTH : 0) +
					(( mCell[cellPos+nCol] == CELL_WALL ) ? WALL_SOUTH : 0);

				//printf("Cell %d %d : situation %d\n",row, col, cellSituation);
				//if no walls or if on a goal : do nothing
				if( cellSituation != 0)
				{
					//check if corner
					if( (cellSituation % 3) == 0 ) 
						mWorkingBoard[cellPos] = cellSituation + CORNER;
					//check if dead-end
					else if( (cellSituation == 7) || (cellSituation == 11) || 
						(cellSituation == 13) || (cellSituation == 14) )
						mWorkingBoard[cellPos] = cellSituation + DEADEND;
					//check if corridor
					else if( (cellSituation % 5) == 0 )
					{
						//if the corridor lead to a dead-end already seen (so W or N)
						if( (mWorkingBoard[cellPos-1] & DEADEND) || 
							(mWorkingBoard[cellPos-nCol] & DEADEND))
							mWorkingBoard[cellPos] = cellSituation + DEADEND;
						//if on the same wall than a corner on the west
						if( (mWorkingBoard[cellPos-1] & (CORNER|POSSIBLE_DEADLOCK)) &&
							(cellSituation & mWorkingBoard[cellPos-1]) )
							mWorkingBoard[cellPos] = cellSituation + POSSIBLE_DEADLOCK;
						//same on the north
						if( (mWorkingBoard[cellPos-nCol] & (CORNER|POSSIBLE_DEADLOCK)) &&
							(cellSituation & mWorkingBoard[cellPos-nCol]) )
							mWorkingBoard[cellPos] = cellSituation + POSSIBLE_DEADLOCK;
					}
					
					//else there is one and only one walls so we just check
					//if we saw a corner before on this same walls
					//first look west
					else if( (mWorkingBoard[cellPos-1] & (CORNER|POSSIBLE_DEADLOCK)) &&
							(cellSituation & mWorkingBoard[cellPos-1]) )
						mWorkingBoard[cellPos] = cellSituation + POSSIBLE_DEADLOCK;
					//then north
					else if( (mWorkingBoard[cellPos-nCol] & (CORNER|POSSIBLE_DEADLOCK)) &&
							(cellSituation & mWorkingBoard[cellPos-nCol]) )
						mWorkingBoard[cellPos] = cellSituation + POSSIBLE_DEADLOCK;
					
				}
				
			}
		}
	}
	
	/*intermediate print*/
	/*uint8_t pR1, pC1;
  for (pR1 = 0; pR1 < nRow; ++pR1)
  {
    for (pC1= 0; pC1 < nCol; ++pC1)
    {
			if ( mWorkingBoard[pR1*nCol+pC1] & DEADEND)
        printf("S");
			else if ( mWorkingBoard[pR1*nCol+pC1] & CORNER)
        printf("D");
      else if ( mWorkingBoard[pR1*nCol+pC1] & POSSIBLE_DEADLOCK)
        printf("I");
			else
        printf(" ");


    }
    printf("\n");
  }
  
  printf("\n\n");
	*/
	for ( int row = nRow-1 ; row >= 0 ; row-- )
	{
		for ( int col = nCol-1 ; col >= 0 ; col-- )
		{
			int cellPos = row*nCol + col;
			
			if ( mCell[cellPos] != CELL_WALL )
			{
				//if corner or dead-end then it's an obvious deadlock
				if ( mWorkingBoard[cellPos] & (CORNER | DEADEND) )
					mCell[cellPos] = CELL_DEADLOCK;

				else if ( mWorkingBoard[cellPos] & POSSIBLE_DEADLOCK )
				{
					//check if south or east is a deadlock
					if( (mCell[cellPos+nCol] == CELL_DEADLOCK) ||
							(mCell[cellPos+1] == CELL_DEADLOCK) )
						mCell[cellPos] = CELL_DEADLOCK;
					
				}
				
				//else if corridor, check if south or east is a dead-end
				else if( mWorkingBoard[cellPos] != 0 && ((mWorkingBoard[cellPos]) % 5) == 0)
				{
					if( (mWorkingBoard[cellPos+1] & DEADEND) || 
						(mWorkingBoard[cellPos+nCol] & DEADEND))
					{
						mWorkingBoard[cellPos] += DEADEND;
						mCell[cellPos] = CELL_DEADLOCK;
					}
				}
			}
		}
	}
	
	//final print
	/*uint8_t pR, pC;
  for (pR = 0; pR < nRow; ++pR)
  {
    for (pC= 0; pC < nCol; ++pC)
    {
      
      switch ( mCell[pR*nCol+pC] )
      {
      case (CELL_WALL):
        printf("#");
        break;
      case (CELL_FLOOR):
        printf(" ");
        break;
      case (CELL_GOAL):
        printf(".");
        break;
			case (CELL_DEADLOCK):
				printf("X");
				break;
      }

    }
    printf("\n");
  }*/
}

bool CBoard::DetectDynamicDeadlock( T_POS newBoxPos , uint8_t boxIdx ) const
{

  uint16_t oldBoxPos = boxesCells[ boxIdx ];

  boxesCells[ boxIdx ] = newBoxPos;

  if ( FormsBlockDeadlock( newBoxPos ) )
  {
    boxesCells[ boxIdx ] = oldBoxPos; 
#if ( LOG_LEVEL & L_DYN_DEADLOCK )
    LOG( L_DYN_DEADLOCK, "Four block detected when trying to move ..." );
    vector<T_POS> marks;
    marks.push_back( oldBoxPos ); // position of the box
    marks.push_back( newBoxPos ); // where the box was intented to be moved
    Print( marks );
    getchar();
#endif
    return true;
  }    

  if ( IsFreezeDeadlock() )
  {
    boxesCells[ boxIdx ] = oldBoxPos; 
#if ( LOG_LEVEL & L_DYN_DEADLOCK )
    LOG( L_DYN_DEADLOCK, "Freeze deadlock detected when trying to move ..." );
    vector<T_POS> marks;
    marks.push_back( oldBoxPos ); // position of the box
    marks.push_back( newBoxPos ); // where the box was intented to be moved
    Print( marks );
    getchar();
#endif
    return true;
  }
    
  boxesCells[ boxIdx ] = oldBoxPos; 
  return false;

}

bool CBoard::IsFreezeDeadlock() const
{
  unordered_set< T_POS > visitedCells;

  for ( uint8_t i = 0 ; i < nBoxes ; ++i )
  {

    visitedCells.clear();
    visitedCells.insert( boxesCells[i] );

    if ( isBoxFrozenHor( boxesCells[i], visitedCells ) && 
         isBoxFrozenVer( boxesCells[i], visitedCells ) )
    {
      // Don't say that it is a freeze deadlock so fast! Is the box in a goal?
      if ( mCell[ boxesCells[i] ]!=CELL_GOAL )
        return true;
    }

  }

  // No freeze deadlock and no solution, we lost time doing this
  return false;

}

bool CBoard::isBoxFrozenHor
( 
  T_POS                    boxPos, 
  unordered_set< T_POS > & visitedCells
) const
{

  if ( mCell[ boxPos-1 ]==CELL_WALL || mCell[ boxPos+1 ]==CELL_WALL )
    return true;
  else if ( mCell[ boxPos-1 ]==CELL_DEADLOCK && 
            mCell[ boxPos+1 ]==CELL_DEADLOCK    ) 
    return true;
  else if ( isBox( boxPos-1 ) && visitedCells.find( boxPos-1 )==visitedCells.end() )
  {
    visitedCells.insert( boxPos-1 );
     if ( isBoxFrozenVer( boxPos-1, visitedCells ) ) return true;
  }
  else if ( isBox( boxPos+1 ) && visitedCells.find( boxPos+1 )==visitedCells.end() )
  {
    visitedCells.insert( boxPos+1 );
    if (  isBoxFrozenVer( boxPos+1, visitedCells ) ) return true;
  }
    
  return false;

}

bool CBoard::isBoxFrozenVer
( 
  T_POS                    boxPos, 
  unordered_set< T_POS > & visitedCells
) const
{

  if ( mCell[ boxPos-nCol ]==CELL_WALL || mCell[ boxPos+nCol ]==CELL_WALL )
    return true;
  else if ( mCell[ boxPos-nCol ]==CELL_DEADLOCK &&
            mCell[ boxPos+nCol ]==CELL_DEADLOCK    )
    return true;
  else if ( isBox( boxPos-nCol ) && visitedCells.find( boxPos-nCol )==visitedCells.end() )
  {
    visitedCells.insert( boxPos-nCol );
    if ( isBoxFrozenHor( boxPos-nCol, visitedCells ) )  return true;
  }
  else if ( isBox( boxPos+nCol ) && visitedCells.find( boxPos+nCol )==visitedCells.end() )
  {
    visitedCells.insert( boxPos+nCol );
    if ( isBoxFrozenHor( boxPos+nCol, visitedCells ) ) return true;
  }
    
  return false;

}

bool CBoard::isBox( T_POS cell ) const
{

  for ( uint8_t i = 0 ; i < nBoxes ; ++i )
  {
    if ( boxesCells[i]==cell )
      return true;
  }
  return false;

}

bool CBoard::FormsBlockDeadlock( T_POS newBoxPos ) const
{
  
  T_POS cellsToCheck[3];
  uint8_t  i;
  bool     isFourBlock;

  // The last movement has placed the box in the right upper corner of the bock
  cellsToCheck[0] = newBoxPos - 1;
  cellsToCheck[1] = newBoxPos + nCol;
  cellsToCheck[2] = newBoxPos + nCol - 1;

  isFourBlock = true;
  for ( i = 0 ; i < 3 ; ++i )
    if ( ! ( isBox( cellsToCheck[i] ) || mCell[cellsToCheck[i]]==CELL_WALL )  )
    {
      isFourBlock = false;
      break;
    }

  if ( isFourBlock )
  {
    // If one of the parts of the block is a box that is not a goal, deadlock
    if ( mCell[ newBoxPos ]!=CELL_GOAL )
      return true;
    for ( i = 0; i < 3 ; ++i )
      if ( isBox( cellsToCheck[i] ) && mCell[ cellsToCheck[i] ]!=CELL_GOAL )  
        return true;
  }

  // The last movement has placed the box in the left upper corner of the bock
  cellsToCheck[0] = newBoxPos + 1;
  cellsToCheck[1] = newBoxPos + nCol;
  cellsToCheck[2] = newBoxPos + nCol + 1;

  isFourBlock = true;
  for ( i = 0 ; i < 3 ; ++i )
    if ( ! ( isBox( cellsToCheck[i] ) || mCell[cellsToCheck[i]]==CELL_WALL )  )
    {
      isFourBlock = false;
      break;
    }

  if ( isFourBlock )
  {
    // If one of the parts of the block is a box that is not a goal, deadlock
    if ( mCell[ newBoxPos ]!=CELL_GOAL )
      return true;
    for ( i = 0; i < 3 ; ++i )
      if ( isBox( cellsToCheck[i] ) && mCell[ cellsToCheck[i] ]!=CELL_GOAL )  
        return true;
  }

  // The last movement has placed the box in the right lower corner of the bock
  cellsToCheck[0] = newBoxPos - 1;
  cellsToCheck[1] = newBoxPos - nCol;
  cellsToCheck[2] = newBoxPos - nCol - 1;

  isFourBlock = true;
  for ( i = 0 ; i < 3 ; ++i )
    if ( ! ( isBox( cellsToCheck[i] ) || mCell[cellsToCheck[i]]==CELL_WALL )  )
    {
      isFourBlock = false;
      break;
    }

  if ( isFourBlock )
  {
    // If one of the parts of the block is a box that is not a goal, deadlock
    if ( mCell[ newBoxPos ]!=CELL_GOAL )
      return true;
    for ( i = 0; i < 3 ; ++i )
      if ( isBox( cellsToCheck[i] ) && mCell[ cellsToCheck[i] ]!=CELL_GOAL )  
        return true;
  }

  // The last movement has placed the box in the left lower corner of the bock
  cellsToCheck[0] = newBoxPos + 1;
  cellsToCheck[1] = newBoxPos - nCol;
  cellsToCheck[2] = newBoxPos - nCol + 1;

  isFourBlock = true;
  for ( i = 0 ; i < 3 ; ++i )
    if ( ! ( isBox( cellsToCheck[i] ) || mCell[cellsToCheck[i]]==CELL_WALL )  )
    {
      isFourBlock = false;
      break;
    }

  if ( isFourBlock )
  {
    // If one of the parts of the block is a box that is not a goal, deadlock
    if ( mCell[ newBoxPos ]!=CELL_GOAL )
      return true;
    for ( i = 0; i < 3 ; ++i )
      if ( isBox( cellsToCheck[i] ) && mCell[ cellsToCheck[i] ]!=CELL_GOAL )  
        return true;
  }

  return false;

}

/* namespace sokoban */ }
